package Service.utils;

import Config.GlobalVariables;

import java.util.*;


public class ShortestPath {
    // TODO: 计算两点之间的最短路径
    private List<List<Integer>> gridList;
    private int rows;
    private int cols;

    // 构造函数
    public ShortestPath(List<List<Integer>> gridList) {
        this.gridList = gridList;
        this.rows = gridList.size();
        this.cols = gridList.get(0).size();
    }

    /**
     * 计算两点之间的最短路径
     *
     * @param start 起点坐标
     * @param end   终点坐标
     * @return 最短路径
     */
    public List<int[]> findShortestPath(int[] start, int[] end) {
        // 根据起点和终点调整路径的实际起点和终点
        int[] adjustedStart = adjustPosition(start);
        int[] adjustedEnd = adjustPosition(end);

        // 使用 A* 算法计算最短路径
        List<int[]> path = aStarShortestPath(adjustedStart, adjustedEnd);

        // 添加起点和终点的调整路径
        if (!Arrays.equals(adjustedEnd, end)) {
            path.add(end);
        }
        if (!Arrays.equals(adjustedStart, start)) {
            path.add(0, start);
        }

        return path;
    }

    /**
     * 调整起点或终点的实际位置
     *
     * @param position 输入位置
     * @return 调整后的实际位置
     */
    private int[] adjustPosition(int[] position) {
        int value = gridList.get(position[0]).get(position[1]);
        int[] adjustedPosition = {-1, -1};

        switch (value) {
            case 0: // 空地
                adjustedPosition = position;
                break;
            case 1, 2: // 货架
                adjustedPosition = findAccessibleSide(position, -1, 1);
                break;
            case 3: // 左侧上货口
                adjustedPosition = new int[]{position[0], position[1] + 1};
                break;
            case 4: // 右侧出货口
                adjustedPosition = new int[]{position[0], position[1] - 1};
                break;
            case 5: // 充电桩
                adjustedPosition = new int[]{position[0] - 1, position[1]};
                break;
            default:
                throw new IllegalArgumentException("未知的网格值: " + value);
        }

        return adjustedPosition;
    }

    /**
     * 寻找货架周围可通行的一侧
     *
     * @param position    当前货架位置
     * @param leftOffset  左侧偏移
     * @param rightOffset 右侧偏移
     * @return 可通行的邻近位置
     */
    private int[] findAccessibleSide(int[] position, int leftOffset, int rightOffset) {
        int row = position[0];
        int col = position[1];

        if (col + leftOffset >= 0 && gridList.get(row).get(col + leftOffset) == 0) {
            return new int[]{row, col + leftOffset};
        } else if (col + rightOffset < cols && gridList.get(row).get(col + rightOffset) == 0) {
            return new int[]{row, col + rightOffset};
        } else {
            throw new IllegalStateException("货架周围没有可通行的位置");
        }
    }

    /**
     * 使用 A* 算法计算两点之间的最短路径
     *
     * @param start 起点
     * @param end   终点
     * @return 最短路径
     */
    private List<int[]> aStarShortestPath(int[] start, int[] end) {
        PriorityQueue<int[]> openSet = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        boolean[][] closedSet = new boolean[rows][cols];

        int[][] gScore = new int[rows][cols];
        for (int[] row : gScore) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        gScore[start[0]][start[1]] = 0;

        int[][][] cameFrom = new int[rows][cols][2];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                cameFrom[i][j] = new int[]{-1, -1};
            }
        }

        openSet.add(new int[]{start[0], start[1], heuristic(start, end)});

        while (!openSet.isEmpty()) {
            int[] current = openSet.poll();
            int currentRow = current[0];
            int currentCol = current[1];

            if (currentRow == end[0] && currentCol == end[1]) {
                return reconstructPath(cameFrom, end);
            }

            closedSet[currentRow][currentCol] = true;

            for (int[] neighbor : getNeighbors(currentRow, currentCol)) {
                int newRow = neighbor[0];
                int newCol = neighbor[1];

                if (closedSet[newRow][newCol] || gridList.get(newRow).get(newCol) != 0) {
                    continue;
                }

                int tentativeG = gScore[currentRow][currentCol] + 1;

                if (tentativeG < gScore[newRow][newCol]) {
                    gScore[newRow][newCol] = tentativeG;
                    cameFrom[newRow][newCol] = new int[]{currentRow, currentCol};
                    int fScore = tentativeG + heuristic(new int[]{newRow, newCol}, end);
                    openSet.add(new int[]{newRow, newCol, fScore});
                }
            }
        }

        return new ArrayList<>();
    }

    // 计算启发值（曼哈顿距离）
    private int heuristic(int[] point, int[] end) {
        return Math.abs(point[0] - end[0]) + Math.abs(point[1] - end[1]);
    }

    // 获取邻居节点
    private List<int[]> getNeighbors(int row, int col) {
        List<int[]> neighbors = new ArrayList<>();
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                neighbors.add(new int[]{newRow, newCol});
            }
        }

        return neighbors;
    }

    // 构造路径
    private List<int[]> reconstructPath(int[][][] cameFrom, int[] end) {
        List<int[]> path = new ArrayList<>();
        int[] current = end;

        while (current[0] != -1 && current[1] != -1) {
            path.add(0, current);
            current = cameFrom[current[0]][current[1]];
        }

        return path;
    }

    // 测试
    public static void main(String[] args) {
        // 示例网格
        GlobalVariables.init();
        ShortestPath pathfinding = new ShortestPath(GlobalVariables.gridList);

        // 起点和终点
        int[] start = {4, 0};
        int[] end = {15, 1};

        // 寻找最短路径
        List<int[]> path = pathfinding.findShortestPath(start, end);

        // 输出路径
        if (!path.isEmpty()) {
            System.out.println("最短路径：");
            for (int[] point : path) {
                System.out.println(Arrays.toString(point));
            }
        } else {
            System.out.println("没有找到路径！");
        }
    }
}

